/*给定一个表示分数的非负整数数组。 玩家 1 从数组任意一端拿取一个分数，
* 随后玩家 2 继续从剩余数组任意一端拿取分数，然后玩家 1 拿，…… 。每次
* 一个玩家只能拿取一个分数，分数被拿取之后不再可取。直到没有剩余分数可取
* 时游戏结束。最终获得分数总和最多的玩家获胜。
* 给定一个表示分数的数组，预测玩家1是否会成为赢家。你可以假设每个玩家的玩法都会使他的分数最大化。
*
* 输入：[1, 5, 233, 7]
* 输出：True
* 解释：玩家 1 一开始选择 1 。然后玩家 2 必须从 5 和 7 中进行选择。无论玩家 2 选择了哪个，玩家 1 都可以选择 233 。
* 最终，玩家 1（234 分）比玩家 2（12 分）获得更多的分数，所以返回 True，表示玩家 1 可以成为赢家。
* */

package Leetcode;

public class leetcode486 {

    public static void main(String[] args) {

        leetcode486 obj = new leetcode486();
        int[] nums = {1, 5, 233, 7};
        System.out.println(obj.PredictTheWinner(nums));
    }

    public boolean PredictTheWinner(int[] nums){

        int len = nums.length;
        //定义dp数组，dp[i][j]表示下标i到j的先手与后手的取值之差
        int[][] dp = new int[len][len];
        //初始化dp数组，dp[i][i]只能取值
        for (int i = 0;i < len;i++){
            dp[i][i] = nums[i];
        }
        //确定遍历顺序
        for (int j = len - 2;j >= 0;j--){
            for (int k = j + 1;k < len;k++){
                //递推公式
                //这里dp[j][k]的值与其两端的值有关，取能得到最大差值的端点
                dp[j][k] = Math.max(nums[j] - dp[j + 1][k], nums[k] - dp[j][k - 1]);
            }
        }
        return dp[0][len - 1] >= 0;
    }
}
